package com.icbc.DataStructuresAndAlgorithms;

/**
 * 二叉排序树
 */
public class BinaryScortTreeDomo {
	public static void main(String[] args) throws Exception{
		int[] a = {7,3};
		BinaryScortTree binaryScortTree = new BinaryScortTree();
		for (int i : a) {
			BinaryScortTree.Node node = new BinaryScortTree.Node(i);
			binaryScortTree.add(node);
		}
		binaryScortTree.inFixOrder();
		System.out.println();
		binaryScortTree.del(7);
		binaryScortTree.inFixOrder();
	}
	
}

/**
 * 排序树
 */
class BinaryScortTree{
	Node root;
	//添加
	public void add(Node node){
		if (root == null){
			root = node;
		}else {
			root.add(node);
		}
	}
	
	//删除
	public void del(int value){
		if (root == null){
			return;
		}
		
		//查找目标节点
		Node targetNode = find(value);
		//判断targetNode是否为null,为null在数中没有此节点
		if (targetNode == null){
			return;
		}
		//判断此树是否只有一个节点
		if (root.left == null && root.right == null){
			root = null;
		}
		//查询它的父节点
		Node parent = findParent(value);
		//如果删除的节点有左右子树
		if (targetNode.left != null && targetNode.right != null){
			//首先要获取该节点右子树的最小节点
			Node node = targetNode.right;
			while(node.left != null){
				node = node.left;
			}
			/*
			 * 将找到的最小节点删除,这里是递归删除,因为在上面时按照node.left为null
			 * 的条件进行查找,所以在递归后一定是按照删除子节点或者删除一颗子树的节点
			 * 方式进行删除节点操作,不会进行无限递归
			 */
			del(node.value);
			//将找到的最小节点值赋值给需要删除的节点
			targetNode.value = node.value;
			return;
		}
		/*
		 * 删除子节点或者有一颗子树的节点
		 * 	在这里由于无论删除的是子节点还是有一颗子树的节点,最后的删除操作
		 *	都是类似于parent.left = targetNode.left这样的操作
		 *  如果targetNode没有一颗子树,那么就相当于parent.left = null
		 *  如果有子树,就把parent.left = targetNode.left就可以了
		 *  所以需要判断该节点的子树是左子树还是右子树
		 */
		Node tar = null;
		tar = targetNode.left != null ? targetNode.left : targetNode.right;
		/*
		 * 判断是左子节点还是右子节点,
		 * 	在这里需要判断parent.left不为null后才能验证parent.left.value跟value相同
		 * 	无论是删除的子节点还是有一颗子树的节点都需要判断
		 */
		if (parent != null) {
			if (parent.left != null && parent.left.value == value) {
				parent.left = tar;
			}
			if (parent.right != null && parent.right.value == value) {
				parent.right = tar;
			}
		} else {
			root = tar;
		}
	}
	
	//查找节点
	public Node find(int value){
		if (root == null){
			return null;
		} else {
			return root.find(value);
		}
	}
	
	//查找父节点
	public Node findParent(int value){
		if (root == null){
			return null;
		} else {
			return root.findParent(value);
		}
	}
	
	//中序遍历
	public void inFixOrder(){
		if (root != null){
			root.inFixOrder();
		}
	}
	
	public Node getRoot() {
		return root;
	}
	
	public void setRoot(Node root) {
		this.root = root;
	}
	
	/**
	 * 二叉树的节点Node
	 */
	static class Node{
		int value;
		Node left;
		Node right;
		
		//构造器
		public Node(int value) {
			this.value = value;
		}
		
		//查找节点
		public Node find(int value){
			if (value == this.value){
				return this;
			}
			
			if (value < this.value && this.left != null){
				return this.left.find(value);
			}else if (value >= this.value && this.right != null){
				return this.right.find(value);
			}else{
				return null;
			}
		}
		//查找节点的父节点
		public Node findParent(int value){
			if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)){
				return this;
			}
			
			if (this.value > value && this.left != null){
				return this.left.findParent(value);
			}else if(this.value <= value && this.right != null){
				return this.right.findParent(value);
			}else{
				return null;
			}
		}
		
		
		//添加方法
		public void add(Node node){
			if (node == null){
				return;
			}
			
			if (node.value < this.value){
				if (this.left == null){
					this.left = node;
				} else {
					this.left.add(node);
				}
			}else{
				if (this.right == null){
					this.right = node;
				} else {
					this.right.add(node);
				}
			}
		}
		
		//中序遍历
		public void inFixOrder(){
			if (this.left != null){
				this.left.inFixOrder();
			}
			System.out.print(this);
			if (this.right != null){
				this.right.inFixOrder();
			}
		}
		
		@Override
		public String toString() {
			return value + " ";
		}
	}
}
